package de.dailab.graphworld.pathfinding;

import java.util.ArrayList;
import java.util.List;

import de.dailab.graphworld.ontology.Edge;
import de.dailab.graphworld.ontology.Node;

public class AStar {

	/**
	 * Branch and Bound to find a shortest path to target node with "luftlinien-entfernung" as heuristic
	 * @param source start node
	 * @param target target node
	 * @return edges that lead to target fastest
	 */
	public static ArrayList<Edge> findPath(Node source, Node target) throws IllegalArgumentException{
		
		if(source.getID()==target.getID()) throw new IllegalArgumentException("Source and target are the same node, nothing to find here!");
		PriorityQueue paths = new PriorityQueue();
		Path actual;
		
		// initialize PriorityQueue with first edges
		for(Edge e : source.getEdges()){
			paths.add(new Path(source,e,target));
		}
		// look for path => expand through graph
		while(true){
			actual = paths.pop();
			
			// shortest path leads to home
			if(actual.getLastNode().getID()==target.getID())
				return actual.getEdges();
			// add new paths
			for(Edge e : actual.getLastNode().getEdges()){
				paths.add(new Path(actual,e));
			}
		}
		
	}

	/**
	 * Branch and Bound to find a shortest path to target node with "luftlinien-entfernung" as heuristic
	 * @param source start node
	 * @param target target node id (node has to be found in the graph first)
	 * @return edges that lead to target fastest
	 */
	public static ArrayList<Edge> findPath(Node source, int id) throws IllegalArgumentException{
			
		return findPath(source,findNode(source,id, new ArrayList<Integer>()));
		
	}
	
	// find a node in the graph by looking for its ID
	private static Node findNode(Node source, int id, List<Integer> visitedNodes){
		visitedNodes.add(source.getID());
		
		if(source.getID()==id) 
			return source;
		else{
			for(Edge e : source.getEdges()){
				Node target = e.getTarget();
				if((!visitedNodes.contains(target.getID()) && ((source = findNode(target,id, visitedNodes))!=null)))
					return source;
			}
			return null;
		}
	}

}
